package com.java.tree.avl;


/**
 * 平衡二叉树测试
 *
 * @author 19252
 * @date 2020/7/29
 */
public class BalancedBinaryTreeDemo {

    public static void main(String[] args) {
        BalancedBinaryTree balancedBinaryTree = new BalancedBinaryTree();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        Node node11 = new Node(11);
        Node node12 = new Node(12);
        // 左旋转测试序列
        /*balancedBinaryTree.addNode(node4);
        balancedBinaryTree.addNode(node3);
        balancedBinaryTree.addNode(node6);
        balancedBinaryTree.addNode(node5);
        balancedBinaryTree.addNode(node7);
        balancedBinaryTree.addNode(node8);*/
        // 下面这个序列用于测试右旋转
        /*balancedBinaryTree.addNode(node10);
        balancedBinaryTree.addNode(node12);
        balancedBinaryTree.addNode(node8);
        balancedBinaryTree.addNode(node9);
        balancedBinaryTree.addNode(node7);
        balancedBinaryTree.addNode(node6);*/

        // 双向旋转测试
        balancedBinaryTree.addNode(node7);
        balancedBinaryTree.addNode(node2);
        balancedBinaryTree.addNode(node1);
        balancedBinaryTree.addNode(node3);
        balancedBinaryTree.addNode(node5);
        balancedBinaryTree.addNode(node6);
        balancedBinaryTree.addNode(node4);
        balancedBinaryTree.addNode(node8);
        balancedBinaryTree.addNode(node9);
        balancedBinaryTree.preOrder();
        System.out.println();
        balancedBinaryTree.infixOrder();
        System.out.println("balancedBinaryTree.treeHeight() = " + balancedBinaryTree.treeHeight());
        System.out.println("balancedBinaryTree.leftTreeHeight() = " + balancedBinaryTree.leftTreeHeight());
        System.out.println("balancedBinaryTree.rightTreeHeight() = " + balancedBinaryTree.rightTreeHeight());
        balancedBinaryTree.getTreeBalanced();
        System.out.println("balancedBinaryTree.treeHeight() = " + balancedBinaryTree.treeHeight());
        System.out.println("balancedBinaryTree.leftTreeHeight() = " + balancedBinaryTree.leftTreeHeight());
        System.out.println("balancedBinaryTree.rightTreeHeight() = " + balancedBinaryTree.rightTreeHeight());
        balancedBinaryTree.preOrder();
        System.out.println();
        balancedBinaryTree.infixOrder();
    }
}

/**
 * 平衡二叉树
 */
class BalancedBinaryTree {
    /**
     * 二叉树的根节点
     */
    Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public int treeHeight() {
        return root.treeHeight();
    }

    public int leftTreeHeight() {
        return this.root.getLeft().treeHeight();
    }

    public int rightTreeHeight() {
        return this.root.getRight().treeHeight();
    }

    /**
     * 树的平衡方法
     */
    public void getTreeBalanced() {
        if (leftTreeHeight() - rightTreeHeight() > 1) {
            twoWayRotation(this.root.getLeft(), true);
            leftRotate();
        } else {
            twoWayRotation(this.root.getRight(), false);
            rightRotate();
        }
    }


    /**
     * 右旋转
     */
    public void rightRotate() {
        Node temp = this.root;
        Node rightRoot = temp.getRight();
        temp.setRight(rightRoot.getLeft());
        rightRoot.setLeft(temp);
        this.root = rightRoot;
    }

    /**
     * 左旋转
     */
    public void leftRotate() {
        Node temp = this.root;
        Node leftRoot = temp.getLeft();
        temp.setLeft(leftRoot.getRight());
        leftRoot.setRight(temp);
        this.root = leftRoot;

    }

    /**
     * 双向旋转
     */
    public void twoWayRotation(Node child, boolean way) {
        if (child.getLeft().treeHeight() - child.getRight().treeHeight() > 1) {
            childLeftToRight(child, way);
        }
        if (child.getRight().treeHeight() - child.getLeft().treeHeight() > 1) {
            childRightToLeft(child, way);
        }
    }

    /**
     * 子结点的左旋转
     */
    public void childLeftToRight(Node child, boolean way) {
        Node newRootNextNode = child.getLeft();
        child.setLeft(newRootNextNode.getRight());
        newRootNextNode.setRight(child);
        if (way){
            this.root.setLeft(newRootNextNode);
        }else {
            this.root.setRight(newRootNextNode);
        }
    }

    /**
     * 子结点的右旋转
     */
    public void childRightToLeft(Node child, boolean way) {
        Node newRootNextNode = child.getRight();
        child.setRight(newRootNextNode.getLeft());
        newRootNextNode.setLeft(child);
        if (way){
            this.root.setLeft(newRootNextNode);
        }else {
            this.root.setRight(newRootNextNode);
        }
    }


    /**
     * 向二叉树中添加结点
     * 按照大小顺序向二叉树中添加结点左边为小于该结点的结点，右边为大于该结点的结点
     *
     * @param node 二叉树的结点
     */
    public void addNode(Node node) {
        Node temp = this.root;
        if (temp == null) {
            this.root = node;
        } else {
            while (true) {
                // 重复添加判断
                if (node.getNo() == temp.getNo()) {
                    System.out.printf("您要添加的 %d 结点已存在！\n", temp.getNo());
                    break;
                }
                // 当前要添加的结点小于root结点，则向左添加
                if (node.getNo() < temp.getNo()) {
                    // 当前的结点的左子结点不为空
                    if (temp.getLeft() != null) {
                        // 就将当前节点变为当前结点的左子结点
                        // 再重新开始比较
                        temp = temp.getLeft();
                    } else {
                        // 完成加入树的操作退出
                        temp.setLeft(node);
                        break;
                    }
                } else {
                    // 当前要添加的结点大于等于root结点，则向右添加
                    if (temp.getRight() != null) {
                        temp = temp.getRight();
                    } else {
                        temp.setRight(node);
                        break;
                    }
                }

            }
        }
    }

    /**
     * 递归删除结点
     * 1. 如果删除的是叶子结点，则删除该结点
     * 2.如果删除的是非叶子结点，则在删除该结点的同时按照排序规则补足删除的结点位置
     *
     * @param no 被删除的结点编号
     */
    public void deleteNode(int no) {
        Node temp = this.root;
        if (temp == null) {
            System.out.println("二叉树为空，没有数据可供删除！");
        } else {
            if (temp.getNo() == no) {
                if (temp.getLeft() == null) {
                    this.root = temp.getRight();
                    return;
                }
                if (temp.getLeft() != null) {
                    Node right = temp.getRight();
                    this.root = temp.getLeft();
                    // 因为二叉树添加结点的规则是左小右大
                    this.root.getLastRightNode().setRight(right);
                    return;
                }
            }
            temp.deleteNode(no);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public Node preOrderSearch(int no) {
        return this.root.preOrderSearch(no);
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public Node infixOrderSearch(int no) {
        return this.root.infixOrderSearch(no);
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        } else {
            System.out.println("二叉树为空！");
        }
    }

    public Node afterOrderSearch(int no) {
        return this.root.afterOrderSearch(no);
    }
}

/**
 * 树的结点
 *
 * @author 19252
 * @date 2020/7/23
 */
class Node {

    /**
     * no 排名
     */
    private int no;

    /**
     * 左结点
     */
    private Node left;

    /**
     * 右结点
     */
    private Node right;

    public Node() {
    }

    public Node(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }

    /**
     * 以当前结点为根节点的树的高度
     *
     * @return 树的高度 int
     */
    public int treeHeight() {
        int height = 1;
        int leftHeight = 0;
        int rightHeight = 0;
        if (this.left != null) {
            leftHeight = this.left.treeHeight();
        }
        if (this.right != null) {
            rightHeight = this.right.treeHeight();
        }
        if (leftHeight > rightHeight) {
            height = height + leftHeight;
        } else {
            height = height + rightHeight;
        }
        return height;
    }

    /**
     * 删除结点并补全
     *
     * @param no 被删除结点的no
     */
    public void deleteNode(int no) {
        // 根节点已经被预处理（根节点没有父结点，不能按下面的逻辑处理）
        Node temp = this;
        // 当前节点的左结点是被删除的结点
        if (temp.getLeft() != null && temp.getLeft().getNo() == no) {
            // left 此时就是需要被删除的结点
            Node left = temp.getLeft();
            // 判断被删除的结点是否有两个子结点
            if (left.getLeft() == null && left.getRight() == null) {
                // 没有直接置空
                temp.setLeft(null);
            }
            // 如果被删除的结点存在右结点，将该右结点上升补全
            else if (left.getLeft() == null && left.getRight() != null) {
                temp.setLeft(left.getRight());
            }
            // 如果被删除的结点只存在左节点就直接将左节点上升补全
            else if (left.getLeft() != null && left.getRight() == null) {
                temp.setLeft(left.getLeft());
            }
            // 左右都存在，就将被删除结点的右结点挂载到左节点的最下层的右结点上
            else if (left.getLeft() != null && left.getRight() != null) {
                left.getLeft().getLastRightNode().setRight(left.getRight());
                temp.setLeft(left.getLeft());
            }
            // 结束删除
            return;
        }

        // 当前节点的右结点是被删除的结点
        if (temp.getRight() != null && temp.getRight().getNo() == no) {
            // right 此时就是需要被删除的结点
            Node right = temp.getRight();
            // 如果right 没有左右结点，直接置空
            if (right.getLeft() == null && right.getRight() == null) {
                temp.setRight(null);
            }
            // 如果 right 只存在右结点，将该右结点上升补全
            else if (right.getLeft() == null && right.getRight() != null) {
                temp.setRight(right.getRight());
            }
            // 如果 right 只存在左结点，将该左结点上升补全
            else if (right.getLeft() != null && right.getRight() == null) {
                temp.setRight(right.getLeft());
            }
            // 如果左右结点都存在，将right 的右结点挂载到左结点的最后右结点上
            else if (right.getLeft() != null && right.getRight() != null) {
                right.getLeft().getLastRightNode().setRight(right.getRight());
                temp.setRight(right.getLeft());
            }
            // 删除查找结束
            return;
        }
        // 向左递归删除查找
        if (temp.getLeft() != null) {
            temp.getLeft().deleteNode(no);
        }
        // 向有递归查找
        if (temp.getRight() != null) {
            temp.getRight().deleteNode(no);
        }
    }

    /**
     * 获取该结点下的最后一个右结点
     *
     * @return 返回一个结点下的最后一个右结点
     */
    public Node getLastRightNode() {
        Node temp = this;
        while (temp.getRight() != null) {
            temp = temp.getRight();
        }
        // 子二叉树最下层的最右边的结点
        return temp;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
            this.getRight().preOrder();
        }
    }

    /**
     * 前序查找
     *
     * @param no 被查找的编号
     * @return 返回被查找到的HeroNode 对象
     */
    public Node preOrderSearch(int no) {
        System.out.println("前序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        Node result = null;
        // 左递归查询
        if (this.getLeft() != null) {
            result = this.getLeft().preOrderSearch(no);
        }
        // 先判断左递归查找是否找到结果
        if (result != null) {
            return result;
        }
        // 没找到在向右递归查找
        if (this.getRight() != null) {
            result = this.getRight().preOrderSearch(no);
        }
        // 直接返回查找结果
        return result;
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }
        System.out.println(this);
        if (this.getRight() != null) {
            this.getRight().infixOrder();
        }
    }

    /**
     * 中序查找
     *
     * @param no 查找的no
     * @return 返回被查找到的HeroNode 对象
     */
    public Node infixOrderSearch(int no) {
        Node result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().infixOrderSearch(no);
        }
        // 左递归的null 判断
        if (result != null) {
            return result;
        }
        System.out.println("中序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        if (this.getRight() != null) {
            result = this.getRight().infixOrderSearch(no);
        }
        return result;
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.getLeft() != null) {
            this.getLeft().afterOrder();
        }
        if (this.getRight() != null) {
            this.getRight().afterOrder();
        }
        System.out.println(this);
    }

    /**
     * 后序查找
     *
     * @param no 查找的no
     * @return 返回被查找到的HeroNode 对象
     */
    public Node afterOrderSearch(int no) {
        Node result = null;
        if (this.getLeft() != null) {
            result = this.getLeft().afterOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        if (this.getRight() != null) {
            result = this.getRight().afterOrderSearch(no);
        }
        System.out.println("后序查找！~~~");
        if (this.getNo() == no) {
            return this;
        }
        return result;
    }
}


